package com.gitee.feizns.explore.data_structure.linked_list.singly.insertionSortList;

/**
 * @author feizns
 * @since 2019/11/11
 */
public class Main {

    public static void main(String[] args) {
        ListNode head = new ListNode(new int[]{5,4,3,2,1});
        ListNode node = insertionSortList(head);
        System.out.println(node);
    }

    public static ListNode insertionSortList(ListNode head) {
        ListNode ret = head;
        if ( head != null && head.next != null ) {
            ListNode prev = head;
            ListNode curt = head.next;
            while ( curt != null ) {
                ListNode next = curt.next;
                if ( curt.val < prev.val ) {
                    prev.next = next;
                    ret = insert(ret, curt);
                }
                prev = curt;
                curt = curt.next;
            }
        }
        return ret;
    }

    private static ListNode insert(ListNode head, ListNode node) {
        ListNode dummy = newListNode(head);
        ListNode prev = dummy;
        ListNode curt = head;
        while ( node.val > curt.val ) {
            prev = curt;
            curt = curt.next;
        }
        prev.next = node;
        node.next = curt;
        return dummy.next;
    }

    private static ListNode newListNode(ListNode next) {
        ListNode ret = new ListNode(0);
        ret.next = next;
        return ret;
    }

}
